package top.minuy.algorithm.sort.select;
/**
 * @author Minuy
 * @time 11:50
 * @date 2021/8/21
 */
public class SelectSort {
    private SelectSort() {}

    /**
     * 选择排序，选择最小的交换
     * @param arr 数组
     * @param <E> 泛型支持
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        // 泛型，实现Comparable接口的类型，Comparable：可比较

        // arr[0...i) 是有序的； arr[i...n) 是无序的；
        for (int i = 0; i < arr.length; i++) {

            // 选择 arr[i...n) 中的最小值的索引
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                // 使用Comparable接口的compareTo方法比较，比目标小，返回值小于0，比目标大，大于0，相等，=0
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

    /**
     * 选择排序，选择最大的交换
     * @param arr 数组
     * @param <E> 泛型支持
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {

        // arr[i...n) 是有序的； arr[0...i) 是无序的；
        for (int i = arr.length-1; i > 0; i--) {

            // 选择 arr[0...i) 中的最大值的索引
            int maxIndex = i;
            for (int j = i; j >= 0; j--) {
                if (arr[j].compareTo(arr[maxIndex]) > 0) {
                    maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }
}
